package day02;

/**
 * @author aiPlusPlus
 * @version 1.0
 * @date 2022/12/2 20:29
 */

import java.util.LinkedList;

/**
 * 给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。
 *
 * 子数组 是数组中 连续 的一部分。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1], k = 1
 * 输出：1
 * 示例 2：
 *
 * 输入：nums = [1,2], k = 4
 * 输出：-1
 * 示例 3：
 *
 * 输入：nums = [2,-1,2], k = 3
 * 输出：3
 */
public class Solution4 {
    public int shortestSubarray(int[] nums, int k) {
        int len = nums.length;
        long []pre = new long[len+1];
        for (int i = 0; i < len; i++) {
            pre[i+1]=pre[i]+nums[i];
        }
        int ans = len+1;
        LinkedList<Integer> stack = new LinkedList<>();
        for (int i = 0; i < len + 1; i++) {
            while (!stack.isEmpty()&&pre[i]-pre[stack.peekFirst()]>=k){
                ans = Math.min(ans,i- stack.pollFirst());
            }
            while (!stack.isEmpty()&&pre[i]>=pre[stack.peekLast()]){
                stack.pollLast();
            }
            stack.add(i);
        }
        return ans<len+1?ans:-1;
    }
}
